﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Threading.Tasks;

namespace Bettzueche.Dampfross
{
    /// <summary>
    /// Die RL-Umwelt oder das Spielbrett.
    /// </summary>
    public class Karte
    {
        // Konstanten für Kartengenerator
        const int Unten  = 0;
        const int Oben   = 1;
        const int Links  = 2;
        const int Rechts = 3;
        const int LinksRechts = 4;
        static HexRichtungen[] ZufRichtungen = (HexRichtungen[])Enum.GetValues(typeof(HexRichtungen));

        HexMapRectFlat<Kachel> _Spielfeld;

        int _rows; // Zeilen A-Z
        int _cols; // Spalten 1-n
        internal HexKoordinate _aktuellePosition;
        Umgebung _aktuelleSicht;
        HexKoordinate _ziel;

        #region Properties

        public Umgebung AktuellerZustand {
            get { return _aktuelleSicht; }
            private set { _aktuelleSicht = value; }
        }

        public HexKoordinate Ziel {
            get { return _ziel; }
            set {
                _ziel = value;
                // eventuell Typ der Zielkachel auf Stadt ändern.
            }
        }

        public bool IsFinal {
            get { return _aktuellePosition == _ziel; }
        }

        #endregion


        #region Konstruktor(en)

        /// <summary>
        /// Intitialisiert eine zufällige Karte der angegebenen Größe. Start und Ziel sind
        /// auf Standardkoordnate (1,1) gesetzt.<para>
        /// Benutze <c>ReSpawnAgent</c> und <c>Ziel</c>, um die Positionen anzupassen.</para>
        /// </summary>
        /// <param name="rows">Zeilen </param>
        /// <param name="cols">Spalten</param>
        public Karte(int rows, int cols)
            : this(Karte.RandomMap(rows, cols), new HexKoordinate(1, 1), new HexKoordinate(1, 1))
        {
        }

        /// <summary>
        /// Initialisiert die Karte mit der angegebenen Hex-Kachelwelt. Start und Ziel sind
        /// auf Standardkoordnate (1,1) gesetzt.<para>
        /// Benutze <c>ReSpawnAgent</c> und <c>Ziel</c>, um die Positionen anzupassen.</para>
        /// </summary>
        /// <param name="map">The map.</param>
        public Karte(HexMapRectFlat<Kachel> map) : this(map, new HexKoordinate(1, 1), new HexKoordinate(1, 1)) {
        }

        /// <summary>
        /// Initialisiert die Karte mit der angegebenen Hex-Kachelwelt. Start und Ziel sind
        /// auf Standardkoordnate (1,1) gesetzt.
        /// <para>
        /// Benutze <c>ReSpawnAgent</c> und <c>Ziel</c>, um die Positionen anzupassen.</para>
        /// </summary>
        /// <param name="map">Die Hex-Welt</param>
        /// <param name="start">Startkoordinate</param>
        /// <param name="ziel">Zielkoordinate</param>
        /// <exception cref="System.ArgumentNullException">map</exception>
        public Karte(HexMapRectFlat<Kachel> map, HexKoordinate start, HexKoordinate ziel) {
            if (map == null)
                throw new ArgumentNullException("map");
            _cols = map.Width;
            _rows = map.Height;
            _Spielfeld = map;
            _aktuellePosition = start;
            Ziel = ziel;
            _aktuelleSicht = ErzeugeSichtfeld(start);
        }

        #endregion


        #region Methoden

        public void MacheSpielzug(HexRichtungen zug, out double wegKosten, out Umgebung neuesSichtfeld) {
            HexKoordinate folgePos = HexMapRectFlat.Move(_aktuellePosition, zug);
            wegKosten = BerechneWegkosten(_aktuellePosition, zug);
            if (IstZugMachbar(folgePos)) {
                _aktuellePosition = folgePos;
                neuesSichtfeld = ErzeugeSichtfeld(folgePos);
                _aktuelleSicht = neuesSichtfeld;
            }
            else {
                neuesSichtfeld = _aktuelleSicht;
            }
        }

        /// <summary>
        /// Setzt Agenten auf die angegebene Position.
        /// </summary>
        /// <param name="position">The position.</param>
        /// <returns>aktueller 'Zustand' / aktuelle Sicht</returns>
        public Umgebung ReSpawnAgent(HexKoordinate position) {
            _aktuelleSicht = ErzeugeSichtfeld(position);
            _aktuellePosition = position;
            return _aktuelleSicht;
        }

        /// <summary>
        /// Erstellt für diese Karte eine zweite mit allen optimalen Wegkosten zum Ziel.
        /// </summary>
        /// <returns></returns>
        /// <remarks>Es wird ein zweite Hexkarte mit <c>DijkstraKacheln</c>erstellt. Mittels des Dijkstra Algorithmus
        /// werden zuerst die kürzesten Pfade zur Zielkoordinate ermittelt. Anschließend werden darauf basierend
        /// auch die Kosten für alle anderen Richtungen einer Kachel ermittelt: Wegkosten zum Nachbar + kürzester Pfad
        /// vom Nachbarn.
        /// Diese Kostenkarte dient zum Vergleich, wie nah die gelernten Kosten (die RL-Schätzfunktion) am Optimum bezüglich
        /// dieser Karte / Umgebung ist.</remarks>
        public HexMapRectFlat<DijkstraKachel> Dijkstra() {
            // Ermittle die kürzesten Wege
            var Graph = new HexMapRectFlat<DijkstraKachel>(_Spielfeld.Height, _Spielfeld.Width);
            Graph[_ziel].Wegkosten = 0;
            var toDoListe = new PriorityQueue<DijkstraKachel>(Graph, (d1, d2) => d1.Wegkosten - d2.Wegkosten);
            var equalComparer = new DijkstraCoordComparer();
            while (toDoListe.Count > 0) {
                //knoten = Knoten in Q mit kleinstem Abstand
                var knoten = toDoListe.Dequeue();
                // Überspringe Wasserfelder
                if (_Spielfeld[knoten.Koordinate].Content.Typ == Kacheltyp.Wasser)
                    continue;
                // für jeden Nachbarn v von u:
                //  falls v in Q:
                //   distanz_update(u,v,abstand[],vorgänger[])   // prüfe Abstand vom Startknoten zu v
                for (int dir = 0; dir < 6; dir++) {
                    HexRichtungen richtung = (HexRichtungen)dir;
                    var nachbarCoord = HexMapRectFlat.Move(knoten.Koordinate, richtung);
                    // richtung vom Nachbar zum Knoten ist entgegengesetzt:
                    richtung = (HexRichtungen)((dir + 3) % 6);
                    if (Graph.Contains(nachbarCoord)) { // <- auf Welt ende achten
                        // wenn Nachbar Wasserfeld, Kosten für Irrweg eintragen und dann überspringen
                        if (_Spielfeld[nachbarCoord].Content.Typ == Kacheltyp.Wasser) {
                            int tmpKosten = knoten.Wegkosten - (int)BerechneWegkosten(knoten.Koordinate, (HexRichtungen)dir);
                            knoten.AlleKosten[dir] = tmpKosten;
                            continue;
                        }
                        var nachbar = Graph[nachbarCoord];
                        // Kosten von Nachbar über 'knoten' ermitteln und ggf. eintragen, wenn geringer als bisher ermittelt.
                        if (toDoListe.Contains(nachbar, equalComparer)) {
                            // Kosten sind als negative Werte gespeichert. Dijkastra funktioniert nur mit positiven Kantengewichten
                            // also imme mit negativen Kosten rechnen
                            int tmpKosten = knoten.Wegkosten - (int)BerechneWegkosten(nachbar.Koordinate, richtung);
                            if (tmpKosten < nachbar.Wegkosten) {
                                nachbar.Wegkosten = tmpKosten;
                                nachbar.Vorganger = richtung;
                                // !!! Hier auch nachbarn aus PrioQueu entfernen und neu einreihen. Damit wieder consistent!!!
                                toDoListe.RemoveFirst(nachbar, equalComparer);
                                toDoListe.Enqueue(nachbar);
                            }
                        }
                    }
                }
            }
            // Fülle die Kosten für alle Richtungen je Kachel
            HexRichtungen[] richtungen = (HexRichtungen[])Enum.GetValues(typeof(HexRichtungen));
            foreach (var kachel in Graph) {
                if (_Spielfeld[kachel.Koordinate].Content.Typ == Kacheltyp.Wasser)
                    continue;
                for (int i = 0; i < richtungen.Length; i++) {
                    if (kachel.Vorganger == richtungen[i]) { // den 'besten' Pfad eintragen
                        kachel.AlleKosten[i] = kachel.Wegkosten;
                        continue;
                    }
                    var nachbarCoord = HexMapRectFlat.Move(kachel.Koordinate, richtungen[i]);
                    if (Graph.Contains(nachbarCoord)) { // <- auf Welt ende achten
                        // Kosten für Wasser-Nachbarn sind bereits eingetragen
                        if (_Spielfeld[nachbarCoord].Content.Typ == Kacheltyp.Wasser)
                            continue;
                        kachel.AlleKosten[i] = Graph[nachbarCoord].Wegkosten - (int)BerechneWegkosten(kachel.Koordinate, richtungen[i]);
                    }
                }
            }
            return Graph;
        }

        /// <summary>
        /// Speichert die Hex-Kachel-Welt in die Datei 'filename'.
        /// </summary>
        /// <param name="filename">The filename.</param>
        /// <returns>true, wenn Speichern erfolgreich; false, wenn Fehler auftrat</returns>
        public bool SafeMapToFile(string filename) {
            FileStream fs = new FileStream(filename, FileMode.Create);
            BinaryFormatter formatter = new BinaryFormatter();
            try {
                formatter.Serialize(fs, _Spielfeld);
                return true;
            }
            catch (SerializationException e) {
                Debug.WriteLine("Failed to serialize. Reason: " + e.Message);
                return false;
            }
            finally {
                fs.Close();
            }
        }

        /// <summary>
        /// Lädt die Hex-Kachel-Welt aus der Datei 'filename'.
        /// </summary>
        /// <param name="filename">The filename.</param>
        /// <returns>HexMap, wenn Laden erfolgreich; null, wenn Fehler auftrat</returns>
        public static HexMapRectFlat<Kachel> LoadMapFromFile(string filename) {
            FileStream fs = new FileStream(filename, FileMode.Open);
            HexMapRectFlat<Kachel> map = null;
            try {
                BinaryFormatter formatter = new BinaryFormatter();
                map = (HexMapRectFlat<Kachel>)formatter.Deserialize(fs);
                return map;
            }
            catch (SerializationException e) {
                Debug.WriteLine("Failed to deserialize. Reason: " + e.Message);
                return null;
            }
            finally {
                fs.Close();
            }
        }

        #endregion


        #region Hilfsmethoden

        internal bool IstZugMachbar(HexKoordinate folgePosition) {
            // Verzicht auf ArrayGrenzen prüfen!
            return _Spielfeld[folgePosition].Content.Typ != Kacheltyp.Wasser;
        }

        private double BerechneWegkosten(HexKoordinate altePos, HexRichtungen zug) {
            var neuePos = HexMapRectFlat.Move(altePos, zug);
            double kosten = -1.0;
            // vom Berg runter
            if (_Spielfeld[altePos].Content.Typ == Kacheltyp.Berg) {
                kosten -= 1.0;
            }
            // auf Berg rauf
            if (_Spielfeld[neuePos].Content.Typ == Kacheltyp.Berg) {
                kosten -= 1.0;
            }
            // über Fluss
            if ( _Spielfeld[altePos].Content.FlussFlags.HasRiverAt(zug) ) {
                kosten -= 1.0;
            }
            // neuPos: Stadt = Ebene -> keine Zusatzkosten
            // neuPos: Wasser -> nur Wegkosten für das Ausgangsfeld
            return kosten;
        }
        
        private Umgebung ErzeugeSichtfeld(HexKoordinate position) {
            Kachel zentrum = _Spielfeld[position];
            // Nachbarfelder
            HexRichtungen[] zuge = (HexRichtungen[])Enum.GetValues(typeof(HexRichtungen));
            Kachel[] nachbarn = new Kachel[zuge.Length];
            for (int i = 0; i < zuge.Length; i++) {
                HexKoordinate coord = HexMapRectFlat.Move(position, zuge[i]);
                nachbarn[i] = _Spielfeld[coord];
            }
            // Richtung
            var richtung = HexMapRectFlat.GibHexRichtung(position, _ziel);
            // Entfernung
            int entfernung = HexMapRectFlat.HexDistance(position, _ziel);
            return new Umgebung(zentrum, richtung, entfernung, nachbarn);
        }

        #endregion


        #region Mapgenerator

        /// <summary>
        /// Erzeugt eine Karte, die außen von Wasserfeldern begrenzt ist und sonst nur aus Ebenen ohne Flüsse besteht.
        /// </summary>
        /// <param name="rows">Anzahl Zeilen</param>
        /// <param name="cols">Anzahl Spalten</param>
        /// <returns>Eine homogene Karte</returns>
        public static HexMapRectFlat<Kachel> HomoMap(int rows, int cols) {
            var map = new HexMapRectFlat<Kachel>(rows, cols);
            var ebene = new KachelContent(Kacheltyp.Ebene, 0);
            int row = 0;
            int col = -1;
            foreach (var feld in map) {
                row += (col + 1) / cols;
                col = (col + 1) % cols;
                if (row == 0) { // erste und letzte Zeile nur Wasser
                    //feld.Content =  new KachelContent(Kacheltyp.Wasser, 0); // kann weg, weil ist eh Standardinitialisierung
                    continue;
                }
                else if (row == (rows - 1)) {
                    // letzte Zeile -> fertig
                    break;
                }
                else if (col == 0 || col == cols - 1) { // erstes und letztes Element Wasser
                    //feld.Content =  new KachelContent(Kacheltyp.Wasser, 0); // kann weg, weil ist eh Standardinitialisierung
                    continue;
                }
                else {
                    feld.Content = ebene;
                }
            }
            return map;
        }

        public static HexMapRectFlat<Kachel> RandomMap(int rows, int cols) {
            var map = new HexMapRectFlat<Kachel>(rows, cols);
            Random random = new Random();
            //double wWasser = 0.05;
            //double wEbene = 0.475;
            //double wBerg = 0.475;

            double w2e = 0.7;
            double w2b = 0.25;
            //double w2w = 0.05;
            double e2e = 0.5;
            double e2b = 0.45;
            //double e2w = 0.05;
            double b2e = 0.45;
            double b2b = 0.5;
            //double b2w = 0.05;

            int row = 0;
            int col = -1;
            Kacheltyp lastTyp = Kacheltyp.Wasser;
            foreach (var feld in map) {
                row += (col + 1) / cols;
                col = (col + 1) % cols;
                if (row == 0) { // erste und letzte Zeile nur Wasser
                    //feld.Content =  new KachelContent(Kacheltyp.Wasser, 0); // kann weg, weil ist eh Standardinitialisierung
                    lastTyp = Kacheltyp.Wasser;
                    continue;
                }
                else if (row == (rows - 1)) {
                    // letzte Zeile -> fertig
                    break;
                }
                else if (col == 0 || col == cols - 1) { // erstes und letztes Element Wasser
                    //feld.Content =  new KachelContent(Kacheltyp.Wasser, 0); // kann weg, weil ist eh Standardinitialisierung
                    lastTyp = Kacheltyp.Wasser;
                    continue;
                }
                else {
                    var rand = random.NextDouble();
                    switch (lastTyp) {
                        case Kacheltyp.Wasser:
                            if (rand <= w2e)
                                feld.Content = new KachelContent(Kacheltyp.Ebene, 0);
                            else if (rand <= (w2e + w2b))
                                feld.Content = new KachelContent(Kacheltyp.Berg, 0);
                            else
                                feld.Content = new KachelContent(Kacheltyp.Wasser, 0);
                            break;
                        case Kacheltyp.Ebene:
                            if (rand <= e2e)
                                feld.Content = new KachelContent(Kacheltyp.Ebene, 0);
                            else if (rand <= (e2e + e2b))
                                feld.Content = new KachelContent(Kacheltyp.Berg, 0);
                            else
                                feld.Content = new KachelContent(Kacheltyp.Wasser, 0);
                            break;
                        case Kacheltyp.Berg:
                            if (rand <= b2e)
                                feld.Content = new KachelContent(Kacheltyp.Ebene, 0);
                            else if (rand <= (b2e + b2b))
                                feld.Content = new KachelContent(Kacheltyp.Berg, 0);
                            else
                                feld.Content = new KachelContent(Kacheltyp.Wasser, 0);
                            break;
                        default:
                            break;
                    }
                    lastTyp = feld.Content.Typ;
                }
            }
            SetzeRivers(map);
            return map;
        }

        static void SetzeRivers(HexMapRectFlat<Kachel> map) {
            // je 16*8 = 128 Felder gibt es potentiell einen Fluss.
            int flussKandidaten = map.Count / 128;
            
            double wNochEinFluss = 0.94;
            Random rand = new Random();
            double zNextRiver = 0.0;
            int anzRivers = 0;
            HexKoordinate coord = new HexKoordinate(0, 0); // erstes Feld; oben links
            // Beginne von einem beliebigen Randfeld und "ziehe" einen Fluss
            do {
                bool istRechts = WahleStartfeld(map, rand, ref coord);
                // ein Startfeld vom Rand wurde gewählt
                // Hinweis: Flüsse entlang der Küstenlinie oder gar im Meer zu ziehen ist zwar "unlogisch", wird aber 
                //          hier ignoriert. Es wird nur geprüft, dass der Pfad nicht IN ein Wasserfeld führt.
                HexRichtungen dir = HexRichtungen.NO;
                HexKoordinate nextCoord = new HexKoordinate();
                bool chosen = false;
                do {
                    chosen = WahleRichtung(map, ref coord, ref dir, ref nextCoord);
                    if (chosen) {
                        // Gegeben: (Ausgangs-)coord, StartEcke rechts oder links (istRechts), nextCoord
                        ZieheFlusslinie(map, ref coord, istRechts, dir, ref nextCoord);
                    }
                    else {
                        // es geht nicht weiter, also Abbruch für diesen Fluss.
                        break;
                        // Hinweis: AnzahlRivers wird weiter unten hochgezählt
                    }
                    // ermittle, ob noch ein Flussstück
                    zNextRiver = rand.NextDouble();
                    coord = nextCoord;
                } while (zNextRiver <= wNochEinFluss); // bis Flusslänge erreicht oder es nicht weitergeht.
                
                // ermittle, ob noch ein Fluss
                zNextRiver = rand.NextDouble();
                anzRivers++;
                // Wenn soviel Flüsse wie Flusskandidaten oder W.keit für noch einen Fluss nicht erfüllt,
                // breche ab.
            } while ((anzRivers < flussKandidaten) && (zNextRiver <= wNochEinFluss));
            // 
        }

        private static bool WahleStartfeld(HexMapRectFlat<Kachel> map, Random rand, ref HexKoordinate coord) {
            // Wähle eine von vier Kanten
            int kante = rand.Next(4);
            bool istRechts = false; // rechte oder linke Ecke eines Feldes?
            switch (kante) {
                case Karte.Unten: // unten
                    //felder = map.GetEnumerator();
                    // setze StartKoordinate auf erstef Feld in letzter Zeile
                    coord = new HexKoordinate(map.Height-1, 0);
                    // fahre fort wie für "oben":
                    goto case Oben;
                case Oben: // oben
                    // gehe zufällig-viele Felder nach rechts, mind. ein, max. Width-2:
                    int col = rand.Next(map.Width-3) + 1;
                    for (int c = 0; c < col; c++) {
                        // (gerade Zeile: SO, ungr. NO)
                        if ((c % 2) == 0)
                            coord = HexMapRectFlat.Move(coord, HexRichtungen.SO);
                        else
                            coord = HexMapRectFlat.Move(coord, HexRichtungen.NO);
                    }
                    // Suche Die rechte oder linke Ecke des Feldes als Ende des Flusses aus:
                    //if (coord.Col == 0) { // Sonderfall Feld 1
                    //    istRechts = true;
                    //}
                    //else if (coord.Col == (map.Width-1)) { // Sonderfall vorletztes Feld
                    //    istRechts = false;
                    //}
                    //else { // sonst
                        //int reLi = rand.Next(2);
                        //istRechts = reLi == 1;
                    //}
                    break;
                case Links: // links
                    //istRechts = true;
                    // coord = new HexKoordinate(0, 0); // ist scon auf 0,0
                    goto case Karte.LinksRechts;
                case Rechts: // rechts
                    //istRechts = false;
                    // von 0,0 Width-1 Felder nach rechts (abwechselnd SO, NO)
                    for (int i = 1; i < map.Width; i++) {
                        var richtung = (i%2 == 0) ? HexRichtungen.NO : HexRichtungen.SO;
                        coord = HexMapRectFlat.Move(coord, richtung);
                    }
                    goto case LinksRechts;
                case LinksRechts: // nur von case 2 oder 3 (links/rechts) erreichbar!
                    // gehe zufällig-viele Felder nach unten, mind. ein, max. Height-2:
                    int row = coord.Row + 1 + rand.Next(map.Height-3);
                    coord = new HexKoordinate(row, coord.Col);
                    break;
                default: // kommt nicht vor
                    break;
            }
            int reLi = rand.Next(2);
            istRechts = reLi == 1;
            return istRechts;
        }

        /// <summary>
        /// Wählt eine zufällige Richtung, von welchem der Fluss kommt und gibt Richtung und Koordinate zurück.
        /// Falls kein Nachbar gefunden wird (alle sind Wasserfelder oder haben schon Fluss) ist die Rückgabe <c>false</c>.
        /// </summary>
        /// <param name="map">The map.</param>
        /// <param name="coord">Die aktuelle Koordinate.</param>
        /// <param name="dir">Referenz auf die zurückzugebende Richtung</param>
        /// <param name="nextCoord">TReferenz auf die zurückzugebende nächste Koordinate</param>
        /// <returns>true, wenn eine Richtung gefunden wurde; false, wenn es nicht weitergeht</returns>
        private static bool WahleRichtung(HexMapRectFlat<Kachel> map, ref HexKoordinate coord, ref HexRichtungen dir, ref HexKoordinate nextCoord) {
            bool chosen = false;
            // Wähle eine Richtung, wo es weitergeht
            Karte.MischeRichtungen();
            for (int i = 0; i < Karte.ZufRichtungen.Length; i++) {
                dir = ZufRichtungen[i];
                nextCoord = HexMapRectFlat.Move(coord, dir);
                if (!map.Contains(nextCoord)) {
                    continue;
                }
                if (map[nextCoord].Content.Typ == Kacheltyp.Wasser) {
                    continue; // nicht auf Wasser
                }
                else if (map[nextCoord].Content.HatFluss) {
                    continue; // nicht auf bereits besuchte Felder (mit Fluss)
                }
                else { // Richtung ist ok
                    chosen = true;
                    break;
                }
            } // Ende 'wähle nextCoord'
            return chosen;
        }

        private static void ZieheFlusslinie(HexMapRectFlat<Kachel> map, ref HexKoordinate coord, bool istRechts, HexRichtungen dir, ref HexKoordinate nextCoord) {
            switch (dir) {
                case HexRichtungen.NO:
                    if (istRechts) {
                        Karte.SetzeFlussFlags(map, nextCoord, HexRichtungen.S);
                        Karte.SetzeFlussFlags(map, nextCoord, HexRichtungen.SO);
                    }
                    else {
                        SetzeFlussFlags(map, coord, HexRichtungen.NW);
                        SetzeFlussFlags(map, coord, HexRichtungen.N);
                    }
                    break;
                case HexRichtungen.N:
                    if (istRechts) {
                        SetzeFlussFlags(map, coord, HexRichtungen.NO);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.SO);
                    }
                    else {
                        SetzeFlussFlags(map, coord, HexRichtungen.NW);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.SW);
                    }
                    break;
                case HexRichtungen.NW:
                    if (istRechts) {
                        SetzeFlussFlags(map, coord, HexRichtungen.NO);
                        SetzeFlussFlags(map, coord, HexRichtungen.N);
                    }
                    else {
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.S);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.SW);
                    }
                    break;
                case HexRichtungen.SW:
                    if (istRechts) {
                        SetzeFlussFlags(map, coord, HexRichtungen.SO);
                        SetzeFlussFlags(map, coord, HexRichtungen.S);
                    }
                    else {
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.N);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.NW);
                    }
                    break;
                case HexRichtungen.S:
                    if (istRechts) {
                        SetzeFlussFlags(map, coord, HexRichtungen.SO);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.NO);
                    }
                    else {
                        SetzeFlussFlags(map, coord, HexRichtungen.SW);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.NW);
                    }
                    break;
                case HexRichtungen.SO:
                    if (istRechts) {
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.N);
                        SetzeFlussFlags(map, nextCoord, HexRichtungen.NO);
                    }
                    else {
                        SetzeFlussFlags(map, coord, HexRichtungen.SW);
                        SetzeFlussFlags(map, coord, HexRichtungen.S);
                    }
                    break;
                default:
                    break;
            }
        }

        /// <summary>
        /// Mischt die Reihenfolge im Array <c>ZufRichtungen</c>.
        /// </summary>
        static void MischeRichtungen() {
            Random random = new Random();
            for (int i = 0; i < Karte.ZufRichtungen.Length; i++) {
                int z = random.Next(Karte.ZufRichtungen.Length);
                HexRichtungen tmp = ZufRichtungen[i];
                ZufRichtungen[i] = ZufRichtungen[z];
                ZufRichtungen[z] = tmp;
            }
        }

        /// <summary>
        /// Setzt die fluss flags.
        /// Bei <c>coors</c> in angegebener Richtung <c>dir</c> das Flussflag zu setzen,
        /// bedeutet gleichzeitig ein Flag in entgegengesetzter Richtung beim Nachbarn.
        /// </summary>
        /// <param name="map">The map.</param>
        /// <param name="coord">The coord.</param>
        /// <param name="dir">The dir.</param>
        static void SetzeFlussFlags(HexMapRectFlat<Kachel> map, HexKoordinate coord, HexRichtungen dir) {
            HexKoordinate nachbar = HexMapRectFlat.Move(coord, dir);
            switch (dir) {
                case HexRichtungen.NO:
                    map[coord].Content = new KachelContent(
                        map[coord].Content.Typ,
                        map[coord].Content.FlussFlags | Rivers.NordOst
                        );
                    map[nachbar].Content = new KachelContent(
                        map[nachbar].Content.Typ,
                        map[nachbar].Content.FlussFlags | Rivers.SudWest
                        );
                    break;
                case HexRichtungen.N:
                    map[coord].Content = new KachelContent(
                        map[coord].Content.Typ,
                        map[coord].Content.FlussFlags | Rivers.Nord
                        );
                    map[nachbar].Content = new KachelContent(
                        map[nachbar].Content.Typ,
                        map[nachbar].Content.FlussFlags | Rivers.Sud
                        );
                    break;
                case HexRichtungen.NW:
                    map[coord].Content = new KachelContent(
                        map[coord].Content.Typ,
                        map[coord].Content.FlussFlags | Rivers.NordWest
                        );
                    map[nachbar].Content = new KachelContent(
                        map[nachbar].Content.Typ,
                        map[nachbar].Content.FlussFlags | Rivers.SudOst
                        );
                    break;
                case HexRichtungen.SW:
                    map[coord].Content = new KachelContent(
                        map[coord].Content.Typ,
                        map[coord].Content.FlussFlags | Rivers.SudWest
                        );
                    map[nachbar].Content = new KachelContent(
                        map[nachbar].Content.Typ,
                        map[nachbar].Content.FlussFlags | Rivers.NordOst
                        );
                    break;
                case HexRichtungen.S:
                    map[coord].Content = new KachelContent(
                        map[coord].Content.Typ,
                        map[coord].Content.FlussFlags | Rivers.Sud
                        );
                    map[nachbar].Content = new KachelContent(
                        map[nachbar].Content.Typ,
                        map[nachbar].Content.FlussFlags | Rivers.Nord
                        );
                    break;
                case HexRichtungen.SO:
                    map[coord].Content = new KachelContent(
                        map[coord].Content.Typ,
                        map[coord].Content.FlussFlags | Rivers.SudOst
                        );
                    map[nachbar].Content = new KachelContent(
                        map[nachbar].Content.Typ,
                        map[nachbar].Content.FlussFlags | Rivers.NordWest
                        );
                    break;
                default:
                    break;
            }

        }

        #endregion


        //private void Parse2ColRowNum(int arrayIndex, out int rowNum, out int colNum) {
        //    rowNum = arrayIndex / _rows;
        //    colNum = arrayIndex % _rows;
        //}

        //internal void Print2Console() {
        //    /* Beispiel:
        //       0   2   4
        //      /¯\1/¯\3/¯\
        // (0)A \W/¯\W/¯\W/
        //      /¯\W/¯\W/¯\
        // (1)B \W/ѳᴓB/¯\B/
        //      /¯\E/ѳᴓBø¯\
        // (2)C \W/¯\Ӝ/ѳ\E/
        //      /¯\E/¯\B/¯\
        // (3)D \W/¯\W/¯\W/
        //       ¯\W/¯\W/¯
                  
        //     */
        //    // TODO NEUE Array-Interpretation!!!!
        //    // Schriftfarbe?
        //    // aktuelle Position?
        //    Console.Clear();
        //    Console.CursorTop = 0;
        //    Console.CursorLeft = 0;
        //    // Zeilenweise:
        //    int idx = 0;
        //    int row;
        //    int col;
        //    for (row = 0; row < _rows; row++) {
        //        // ungerade Reihen sind um 2 Zeichen versetzt:
        //        Console.CursorLeft = 0 + (row % 2) * 2;
        //        for (col = 0; col < _cols; col++) {
        //            Kachel kachel = _Spielfeld[idx];
        //            // ...
        //            // Oberes Spielfed ausgeben, inklusive Flüsse
        //            if (kachel.FlussFlags > 0) {
        //                // NordWest Fluss oder Kante
        //                if ((_Spielfeld[idx].FlussFlags & Spielzug.NordWest) == Spielzug.NordWest) {
        //                    Console.Write(Karte.FlussNW);
        //                }
        //                else {
        //                    Console.Write(Karte.KanteNW);
        //                }
        //                // Nord Fluss oder Kante
        //                if ((_Spielfeld[idx].FlussFlags & Spielzug.Nord) == Spielzug.Nord) {
        //                    Console.Write(Karte.FlussN);
        //                }
        //                else {
        //                    Console.Write(Karte.KanteN);
        //                }
        //                // NordOst Fluss oder Kante
        //                if ((_Spielfeld[idx].FlussFlags & Spielzug.NordOst) == Spielzug.NordOst) {
        //                    Console.Write(Karte.FlussNO);
        //                }
        //                else {
        //                    Console.Write(Karte.KanteNO);
        //                }
        //            }
        //            else {
        //                Console.Write(Karte.KanteNW + Karte.KanteN + Karte.KanteNO);
        //            }
        //            // Unteres Spielfeld ausgeben - OHNE Flüsse (Flüsse SO und SW werden ggf.
        //            // bei der nächsten Zeile als NO- bzw. NW-Flüsse ausgegeben).
        //            // Cursor versetzen
        //            Console.CursorTop++;
        //            Console.CursorLeft -= 3; // um 3 Zeichen der oberen Hälftezurücksetzen.
        //            char typ;
        //            switch (_Spielfeld[idx].Typ) {
        //                case Kacheltyp.Wasser:
        //                    typ = Karte.CWasser;
        //                    break;
        //                case Kacheltyp.Ebene:
        //                    typ = Karte.CEbene;
        //                    break;
        //                case Kacheltyp.Berg:
        //                    typ = Karte.CBerg;
        //                    break;
        //                case Kacheltyp.Stadt:
        //                    typ = Karte.CStadt;
        //                    break;
        //                default:
        //                    typ = '?';
        //                    break;
        //            }
        //            Console.Write(Karte.KanteNO + typ + Karte.KanteNW);
        //            // Cursorposition fürs nächste Feld in der Reihe:
        //            Console.CursorTop--;
        //            // Cursor ein weiter setzen, weil sonst die Typ-Bezeichnug des NO-Nachbarn überschrieben wird.
        //            Console.CursorLeft++;
        //            idx++;
        //        } // Ende Durchlauf der Kacheln einer Reihe
        //        Console.CursorTop++; // auf obere Hälfte der nächsten Reihe (= untere Hälfte aktuelle Reihe)
        //        // CursorLeft wird zu Beginn der Schleife gesetzt.
        //    } // Ende "alle Reihen"
        //    // Abschluss der unteren Reihe
        //    Console.CursorTop++;
        //    Console.CursorLeft = 0 + _rows % 2;
        //    for (int i = 0; i < _cols; i++) {
        //        Console.Write(' ' + Karte.KanteN + "  ");
        //    }
        //    Console.WriteLine();

        //    // CursorPos zwischenspeichern
        //    int cCol = Console.CursorLeft;
        //    int cRow = Console.CursorTop;
        //    // Setze aktuelle Position
        //    Parse2ColRowNum(_aktuellePosition, out row, out col);
        //    Console.SetCursorPosition(4*col + 1, row +1);
        //    // ungerade Reihen sind um 2 Zeichen versetzt; TypZeichen auf Position 1 im Feld:
        //    Console.CursorLeft += 1 + (row % 2) * 2; // (row & 0x1) << 1;
        //    Console.Write(Karte.CPosition);
        //    Console.SetCursorPosition(cCol, cRow);
        //}

        internal const char FlussNO = 'ᴓ';
        internal const char FlussN = 'ѳ';
        internal const char FlussNW = 'ø';
        internal const char KanteNO = '\\';
        internal const char KanteN = '¯';
        internal const char KanteNW = '/';
        internal const char CWasser = 'W';
        internal const char CEbene = 'E';
        internal const char CBerg = 'B';
        internal const char CStadt = 'S';
        internal const char CPosition = 'Ӝ';



        class DijkstraCoordComparer : IEqualityComparer<DijkstraKachel>, IComparer<DijkstraKachel>
        {

            public bool Equals(DijkstraKachel x, DijkstraKachel y) {
                //Check whether the compared objects reference the same data. 
                if (Object.ReferenceEquals(x, y))
                    return true;

                //Check whether any of the compared objects is null. 
                if (Object.ReferenceEquals(x, null) || Object.ReferenceEquals(y, null))
                    return false;

                return x.Koordinate == y.Koordinate;
            }

            public int GetHashCode(DijkstraKachel obj) {
                return obj.Koordinate.GetHashCode();
            }

            public int Compare(DijkstraKachel x, DijkstraKachel y) {
                if (Object.ReferenceEquals(x, y))
                    return 0;
                if (Object.ReferenceEquals(x, null) && y != null)
                    return 1;
                if (Object.ReferenceEquals(y, null) && x != null)
                    return -1;
                return x.Koordinate.GetHashCode() - y.Koordinate.GetHashCode();
            }
        }
    }
}
